Q: Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?
Solution: Euler’s Identity says V – E + R = 1+ number of connected components.
Q: The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is ________
Solution: There can be at most, n*n edges in an undirected graph.
Q: Number of vertices with odd degrees in a graph having a eulerian walk is ________
Solution: If the start and end vertices for the path are same the answer would be 0 otherwise 2.
Q: How many of the following statements are correct? i) All cyclic graphs are complete graphs. ii) All complete graphs are cyclic graphs. iii) All paths are bipartite. iv) All cyclic graphs are bipartite. v) There are cyclic graphs which are complete.
Solution: Statements iii) and v) are correct.
Q: All paths and cyclic graphs are bipartite graphs.
Solution: Only paths and even cycles are bipartite graphs.
Q: What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
Solution: Only the first and the last vertex would have degree 1, others would be of degree 2.
Q: All trees with n vertices consists of n-1 edges.
Solution: A trees is acyclic in nature.
Q: What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
Solution: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.
Q: Dijkstra’s Algorithm will work for both negative and positive weights?
Solution: Dijkstra’s Algorithm assumes all weights to be non-negative.
Q: A graph having an edge from each vertex to every other vertex is called a ___________
Solution: This is a part of the nomenclature followed in Graph Theory.
| You Have Score | /10 |